﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 九连环
{
    public class Solution
    {
        /// <summary>
        /// 全为true时解答结束
        /// </summary>
        public bool[] flag;
        public int n;
        public int step;
        public int th = 0;
        public Solution parent = null;

        public Solution(int n)
        {
            this.n = n;
            this.flag = new bool[n];
            for(int i = 0; i < n; i++)
            {
                flag[i] = false;
            }
        }

        public Solution (Solution parent,int step)
        {
            this.n = parent.n;
            this.flag = (bool[])parent.flag.Clone();
            this.step = step;
            this.th = parent.th + 1;
            this.parent = parent;

            this.flag[step] = !this.flag[step];
        }

        public List<int> Steps()
        {
            List<int> steps = new();
            for (int i = 0; i < n; i++)
            {
                if (CanMove(i))
                {
                    steps.Add(i);
                }
            }
            return steps;
        }

        public bool CanMove(int i)
        {
            if (i == 0)
            {
                return true;
            }
            else
            {
                if (flag[i - 1])
                {
                    return false;
                }

                for(int j = 0; j <= i - 2; j++)
                {
                    if (!flag[j])
                    {
                        return false;
                    }
                }
            }

            return true;
        }

        public bool Succes()
        {
            for(int i = 0; i < n; i++)
            {
                if (!flag[i])
                {
                    return false;
                }
            }
            return true;
        }

        public int Key()
        {
            int key = 0;
            for(int i = 0; i < n; i++)
            {
                if (flag[i])
                {
                    key |= (1 << i);
                }
            }
            return key;
        }
    }
}
